#pragma once

namespace boh
{
	template<class K>
	struct BSTreeNode
	{
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;

		BSTreeNode(const K& key)
			:_key(key)
			, _left(nullptr)
			, _right(nullptr)
		{}
	};

	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;

	public:
		BSTree()
			:_root(nullptr)
		{}

		bool Insert(const K& key)
		{
			return _Insert(_root, key);
		}

		bool Find(const K& key)
		{
			return _Find(_root, key);
		}

		bool Erase(const K& key)
		{
			return _Erase(_root, key);
		}

		void Inorder()
		{
			_Inorder(_root);
			cout << endl;
		}

	private:
		bool _Insert(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}

			if (root->_key > key)
			{
				return _Insert(root->_left, key);
			}
			else if (root->_key < key)
			{
				return _Insert(root->_right, key);
			}
			else
			{
				return false;
			}
		}

		bool _Find(Node* root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}

			if (root->_key > key)
			{
				return _Find(root->_left, key);
			}
			else if (root->_key < key)
			{
				return _Find(root->_right, key);
			}
			else
			{
				return true;
			}
		}

		bool _Erase(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}

			if (root->_key > key)
			{
				return _Erase(root->_left, key);
			}
			else if (root->_key < key)
			{
				return _Erase(root->_right, key);
			}
			else
			{
				Node* del = root;
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* minright = root->_right;
					while (minright->_left)
					{
						minright = minright->_left;
					}
					swap(root->_key, minright->_key);
					return _Erase(root->_right, key);
				}
				delete del;
				return true;
			}
		}

		void _Inorder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Inorder(root->_left);
			cout << root->_key << ' ';
			_Inorder(root->_right);
		}

		Node* _root;
	};

	void test()
	{
		BSTree<int> t;
		int arr[] = { 12,4,565,43,87,97,40,543,78,19 };
		for (auto e : arr)
		{
			t.Insert(e);
		}
		t.Inorder();

		cout << t.Find(565) << endl;
		
		t.Erase(565);
		t.Erase(543);
		t.Inorder();
	}
}